//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// hash_table_bucket_page.cpp
//
// Identification: src/storage/page/hash_table_bucket_page.cpp
//
// Copyright (c) 2015-2021, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "storage/page/hash_table_bucket_page.h"
#include "common/logger.h"
#include "common/util/hash_util.h"
#include "storage/index/generic_key.h"
#include "storage/index/hash_comparator.h"
#include "storage/table/tmp_tuple.h"

namespace bustub {

// set the y'th bit to 1
#define SETBIT(x, y) (x) |= (1 << (y))
// reset the y'th bit to 0
#define RESETBIT(x, y) (x) &= ~(1 << (y))

template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_BUCKET_TYPE::GetValue(KeyType key, KeyComparator cmp, std::vector<ValueType> *result) {
    bool f = false;
    for (uint32_t i = 0; i < BUCKET_ARRAY_SIZE; ++i) {
        if (!IsOccupied(i)) {
            break;
        }
        if (IsReadable(i) && cmp(KeyAt(i), key) == 0) {
            result->push_back(ValueAt(i));
            f = true;
        }
    }
    return f;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_BUCKET_TYPE::Insert(KeyType key, ValueType value, KeyComparator cmp) {
    int idx = -1;
    for (uint32_t i = 0; i < BUCKET_ARRAY_SIZE; ++i) {
        if (IsReadable(i) && cmp(KeyAt(i), key) == 0 && ValueAt(i) == value) {
            return false;
        }
        if (!IsReadable(i)) {
            if (idx == -1) {
                idx = i;     
            }
        }
    }
    // full
    if (idx == -1) {
        return false;
    }

    array_[idx] = {key, value};
    SetOccupied(idx);
    SetReadable(idx);

    return true;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_BUCKET_TYPE::Remove(KeyType key, ValueType value, KeyComparator cmp) {
    bool f = false;
    for (uint32_t i = 0; i < BUCKET_ARRAY_SIZE; ++i) {
        if (!IsOccupied(i)) {
            break;
        }
        if (IsReadable(i) && cmp(KeyAt(i), key) == 0 && ValueAt(i) == value) {
            f = true;
            RemoveAt(i);
            break;
        }
    }
    return f;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
KeyType HASH_TABLE_BUCKET_TYPE::KeyAt(uint32_t bucket_idx) const {
    return array_[bucket_idx].first;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
ValueType HASH_TABLE_BUCKET_TYPE::ValueAt(uint32_t bucket_idx) const {
    return array_[bucket_idx].second;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void HASH_TABLE_BUCKET_TYPE::RemoveAt(uint32_t bucket_idx) {
    RESETBIT(readable_[bucket_idx >> 3], bucket_idx & 7);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_BUCKET_TYPE::IsOccupied(uint32_t bucket_idx) const {
    // bucket_idx & 7 == bucket_idx % 8
    return (occupied_[bucket_idx >> 3] & (1 << (bucket_idx & 7))) != 0;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void HASH_TABLE_BUCKET_TYPE::SetOccupied(uint32_t bucket_idx) {
    SETBIT(occupied_[bucket_idx >> 3], bucket_idx & 7);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_BUCKET_TYPE::IsReadable(uint32_t bucket_idx) const {
    return (readable_[bucket_idx >> 3] & (1 << (bucket_idx & 7))) != 0;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void HASH_TABLE_BUCKET_TYPE::SetReadable(uint32_t bucket_idx) {
    SETBIT(readable_[bucket_idx >> 3] ,bucket_idx & 7);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_BUCKET_TYPE::IsFull() {
    auto size = BUCKET_ARRAY_SIZE >> 3;
    for (uint32_t i = 0 ; i < size; ++i) {
        if (readable_[i] != 0xff) {
            return false;
        }
    }
    auto rest = BUCKET_ARRAY_SIZE & 7;
    return readable_[size] == ((1 << rest) - 1);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
uint32_t HASH_TABLE_BUCKET_TYPE::NumReadable() {
    uint32_t size = BUCKET_ARRAY_SIZE >> 3;
    uint32_t ret = 0;
    for (uint32_t i = 0; i < size; ++i) {
        auto byte = readable_[i];
        while (byte != 0) {
            byte &= (byte - 1);
            ++ret;
        }
    }
    auto rest = BUCKET_ARRAY_SIZE & 7;
    if (rest != 0) {
        auto byte = readable_[size];
        while (byte != 0) {
            byte &= (byte - 1);
            ++ret;
        }
    } 
    return ret;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_BUCKET_TYPE::IsEmpty() {
    auto size = BUCKET_ARRAY_SIZE >> 3;
    for (uint32_t i = 0; i < size; ++i) {
        if (readable_[i] != 0x00) {
            return false;
        }
    }
    auto rest = BUCKET_ARRAY_SIZE & 7;
    return (readable_[size] & ((1 << rest) - 1)) == 0;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void HASH_TABLE_BUCKET_TYPE::PrintBucket() {
  uint32_t size = 0;
  uint32_t taken = 0;
  uint32_t free = 0;
  for (size_t bucket_idx = 0; bucket_idx < BUCKET_ARRAY_SIZE; bucket_idx++) {
    if (!IsOccupied(bucket_idx)) {
      break;
    }

    size++;

    if (IsReadable(bucket_idx)) {
      taken++;
    } else {
      free++;
    }
  }

  LOG_INFO("Bucket Capacity: %lu, Size: %u, Taken: %u, Free: %u", BUCKET_ARRAY_SIZE, size, taken, free);
}

// DO NOT REMOVE ANYTHING BELOW THIS LINE
template class HashTableBucketPage<int, int, IntComparator>;

template class HashTableBucketPage<GenericKey<4>, RID, GenericComparator<4>>;
template class HashTableBucketPage<GenericKey<8>, RID, GenericComparator<8>>;
template class HashTableBucketPage<GenericKey<16>, RID, GenericComparator<16>>;
template class HashTableBucketPage<GenericKey<32>, RID, GenericComparator<32>>;
template class HashTableBucketPage<GenericKey<64>, RID, GenericComparator<64>>;

// template class HashTableBucketPage<hash_t, TmpTuple, HashComparator>;

}  // namespace bustub
